User blog:Deedlit11/Ordinal notations II: Up to the Bachmann-Howard ordinal
Okay, I promised to blog about ordinal notations. I thought I would start by going over the basic notations up to the Bachmann-Howard ordinal. The \(\psi\) function I will start with the basic \(\psi\) function, invented by Wolfram Pohlers. It is defined as follows: \(C_0 (\alpha) = \lbrace 0, \Omega \rbrace \) \(C_{n+1} (\alpha) = \lbrace \beta + \gamma, \omega^{\beta}, \psi(\delta) | \beta, \gamma, \delta \in C_n (\alpha); \delta < \alpha \rbrace \) \(C (\alpha) = \bigcup_{n = 1}^{\infty} C_n (\alpha) \) \(\psi (\alpha) = \min \lbrace \beta | \beta \not\in C(\alpha) \rbrace \) This may appear confusing at first, especially since \(\psi\) appears in the definition of C and C appears in the definition of \(\psi\). The important thing to realize is that this is an inductive definition. First we define C(0), which does not depend on any value of \(\psi\); then we define \(\psi(0)\), which depends on C(0) only; then we define C(1), which depends on \(\psi(0)\), and so on. \(C(\alpha)\) is defined to be \(\lbrace 0, \Omega \rbrace \) closed under a bunch of operations. C(0) is \(\lbrace 0, \Omega \rbrace \) closed under addition and the function \(\beta \mapsto \omega^\beta\). After some thought, you will realize that this will generate all ordinals less than \(\varepsilon_0\), but not \(\varepsilon_0\) itself. So \(\psi(0)\), which is the smallest ordinal not in C(0), will be \(\varepsilon_0\). C(1) will be \(\lbrace 0, \Omega, \varepsilon_0 \rbrace \) closed under addition and the function \(\beta \mapsto \omega^\beta\), so it will contain all ordinals less than \(\varepsilon_1\), and \(\psi(1)\) will be \(\varepsilon_1\). This pattern will continue, and \(\psi(\alpha)\) will be \(\varepsilon_{\alpha}\) for quite a while. But not forever! The crucial point occurs when \(\alpha = \varphi(2, 0)\), that is, the first ordinal \(\alpha\) where \(\varepsilon_{\alpha} = \alpha\). We will indeed get, as expected, that \(C(\varphi(2,0)\) will contain all ordinals less than \(\varepsilon_{\varphi(2,0)} = \phi(2,0)\), but not \(\varphi(2,0)\) itself. So \(\psi(\varphi(2,0))\) will be \(\varphi(2,0)\), following the pattern. But \(C(\varphi(2,0) + 1)\) will not contain \(\varphi(2,0)\)! Normally, \(C(\alpha + 1)\) adds \(\psi(\alpha)\) to the set, but according to the definition, this only occurs if \(\alpha\) is already in \(C(\alpha + 1)\). Since \(\varphi(2,0)\) is not already in \(C(\varphi(2,0) + 1)\), it will not get added. So \(C(\varphi(2,0) + 1)\) adds no new ordinals to the set, and \(\psi(\varphi(2,0)+1)\) will be \(\varphi(2,0)\) again. Similarly, \(\psi(\varphi(2,0) + 2\) will be \(\varphi(2,0)\), and so on for higher values of \(\psi\). But again, this does not continue forever; it will continue until \(\psi(\Omega)\). \(\psi(\Omega)\) will still be \(\varphi(2,0)\). But now examine \(C(\Omega + 1)\); now we _do_ have \(\Omega)\) in \(C(\Omega + 1)\), so we will add \(\psi(\Omega) = \varphi(2,0)\) to \(C(\Omega + 1)\), and the other rules will add all other ordinals up to \(\varepsilon_{\varphi(2,0) + 1}\), so \(\psi(\Omega + 1) = \varepsilon_{\varphi(2,0) + 1}\). Continuing, we have \(\psi(\Omega + \alpha) = \varepsilon_{\varphi(2,0) + \alpha}\), up until we reach \(\alpha = \varphi(2,1)\), where we will get stuck again. We eventually get \(\psi(\Omega*2) = \varphi(2,1)\), and get unstuck again, until we get stuck at \(\alpha = \varphi(2,2)\). In general, we will have \(\psi(\Omega(1 + \alpha) + \beta) = \varepsilon_{\varphi(2, \alpha) + \beta}\), provided that \(\beta < \varphi(2, \alpha + 1)\), and \(\alpha < \varphi(3, 0)\). \(\varphi(3,0)\) is where we get stuck even at levels of \(\Omega\); we don't get unstuck until we reach \(\psi(\Omega^2)\). Thus we have \(\psi(\Omega^2) = \varphi(3,0)\), and in general we will have \(\psi(\Omega^{\alpha}(1 + \beta)) = \varphi(1 + \alpha, \beta)\). Again, this doesn't hold if \(\alpha\) is too large; we eventually get stuck even for powers of \(\Omega\). This occurs at the first ordinal for which \(\psi(\Omega^{\alpha}) = \alpha\), that is, the ordinal \(\Gamma_0\). We remain stuck until we reach \(\psi (\Omega^{\Omega}) = \Gamma_0\). We are starting to see a general pattern; in \(\psi\), \(\Omega\) functions as a diagonalization operator, where if f is a function of the proper form, \(\psi(f(\Omega))\) will be the smallest ordinal such that \(\psi(f(\alpha)) = \alpha\). So \(\psi(\Omega^\Omega)\) is the smallest ordinal such that \(\psi(\Omega^{\alpha}) = \alpha\), \(\psi(\Omega^{\Omega^\Omega})\) is the smallest ordinal such that \(\psi(\Omega^{\Omega^{\alpha}}) = \alpha\), and \(\psi(\Omega^{\Omega^\Omega} + \Omega^{\Omega^\omega + \Omega^5 * 4})\) is the smallest ordinal such that \(\psi(\Omega^{\Omega^\Omega} + \Omega^{\Omega^\omega + \Omega^5 * 3 + \Omega^4 * \alpha}) = \alpha\). Some important ordinals: \(\psi(\Omega^{\Omega^{\omega}})\) is the Small Veblen Ordinal, and \(\psi(\Omega^{\Omega^{\Omega}})\) is the Large Veblen Ordinal. Comparing with Schutte's Klammersymbolen, we have \(\psi(\Omega^{\Omega^{a_1} b_1 + \Omega^{a_2} b_2 + \ldots + \Omega^{a_n} b_n} (1 + c)) = (b_1 @ 1 + a_1, b_2 @ 1 + a_2, \ldots, b_n @ 1 + a_n, c @ 0)\). The \(\theta\) function Here is the definition of Feferman's original \(\theta\) function: \(C_0 (\alpha, \beta) = \beta \cup \lbrace 0, \Omega \rbrace \) \(C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \omega^{\gamma}, \theta(\eta, \gamma) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha \rbrace \) \(C (\alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\alpha, \beta) \) \(In (\alpha) = \lbrace \beta | \beta \notin C (\alpha, \beta) \rbrace \) \(\theta (\alpha, \beta) = \) the \(\beta\)th ordinal in \(In (\alpha)\) So, for example, \(C (0, \beta)\) contains the ordinals less than \(\beta\) closed under the functions + and \(\alpha \rightarrow \omega^{\alpha}\), so it will contain all ordinals less than the smallest epsilon ordinal greater than or equal to \(\beta\). So \(In(0)\) will contain the epsilon ordinals, and \(\theta(0, \beta) = \varepsilon_{\beta}\). Similarly, \(\theta(1,\beta) = \varphi(2, \beta)\), and the pattern continues until the values hit the \(\Gamma\) ordinals. So \(\theta (\Omega, \beta) = \Gamma_{\beta}\). In general, we will have the following relationship between \(\theta\) and \(\psi\): \(\theta (\alpha, \beta) = \psi (\Omega^{\alpha} (1 + \beta))\). The \(\vartheta\) function \(C_0 (\alpha, \beta) = \beta \cup \lbrace 0, \Omega \rbrace \) \(C_{n+1} (\alpha, \beta) = \lbrace \gamma + \delta, \omega^{\gamma}, \vartheta(\eta) | \gamma, \delta, \eta \in C_n (\alpha, \beta); \eta < \alpha \rbrace \) \(C (\alpha, \beta) = \bigcup_{n = 1}^{\infty} C_n (\alpha, \beta) \) \(\vartheta (\alpha) = \min \lbrace \beta < \Omega | C(\alpha, \beta) \cap \Omega \subseteq \beta \wedge \alpha \in C(\alpha, \beta) \rbrace \) This is similar to the \(\theta\) function, but it is a one variable function. Also, whereas \(\theta(0, \alpha) = \varepsilon_\alpha\) up until \(\alpha = \varphi (2,0)\) and then stays fixed at \(\varphi(2,0)\), we have \(\vartheta(\alpha) = \varepsilon_\alpha\) up until \(\alpha = \varphi (2,0)\) and then skips over \(\varphi(2,0\); so \(\vartheta(\varphi(2,0) + \alpha) = \varepsilon_{\varphi(2,0) + 1 + \alpha}\) for \(\alpha < \varphi(2,1)\). \(\vartheta(\alpha)\) then skips over \(\varphi(2,1)\), and in general all \(\varphi(2, \beta)\) for all \(\beta\). Conveniently, ordinals of the form \(\varphi(2, \alpha)\) can be represented by \(\vartheta(\Omega + \alpha)\), which runs through all values of \(\varphi(2, \alpha)\) except for ordinals of the form \(\varphi(3, \alpha)\), and so on. In fact, the \(\vartheta\) function is a 1-1 function from \(\varepsilon_{\Omega+1}\) to \(\Omega\), which is convenient for some proofs. For appropriate ordinals, we have \(\theta(\alpha, \beta) = \vartheta (\Omega * \alpha + \beta)\). Standard form for the \(\psi\) function Here we define standard form for the \(\psi\) function, so that each ordinal less than \(\psi(\varepsilon_{\Omega + 1})\) has a standard form; standard form for the \(\theta\) and \(\vartheta\) functions can be defined similarly. The additively principal ordinals are the ordinals of the form \(\omega^\alpha\). (They are called additively principal since they are precisely the ordinals \(\alpha\) such that, if \(\beta, \gamma < \alpha\), then \(\beta + \gamma < \alpha\).) The standard form for 0 is 0. If \(\alpha\) is not additively principal, then the standard form for \(\alpha\) is \(\alpha = \alpha_1 + \alpha_2 + \ldots + \alpha_n\), where the \(\alpha_i\) are principal ordinals with \(\alpha_1 \ge \alpha_2 \ge \ldots \ge \alpha_n\), and the \(\alpha_i\) are expressed in standard form. If \(\alpha\) is countable and additively principal, but not an epsilon ordinal, then the standard form for \(\alpha\) is \(\alpha = \omega^{\beta}\), where \(\beta\) is expressed in standard form. If \(\alpha\) is uncountable and additively principal, then the standard form for \(\alpha\) is \(\alpha = \Omega^{\gamma} \delta\) with \(\delta\) a countable additively principal ordinal, and \(\gamma\) and \(\delta\) expressed in standard form. If \(\alpha\) is a countable epsilon ordinal, then it is expressible in the form \(\psi(\beta)\); we choose \(\beta\) so that \(\beta \in C(\beta)\). (This is always possible for \(\alpha < \psi(\varepsilon_{\Omega + 1})\), or else the \(\psi\) function would stabilize and never grow anymore.). Then the normal form for \(\alpha\) is \(\alpha = \psi (\beta)\) with \(\beta\) expressed in standard form. Fundamental sequences for the \(\psi\) function Here we define fundamental sequences for the \(\psi\) function; fundamental sequences for the \(\theta\) and \(\vartheta\) functions can be defined similarly. First, we express a given ordinal \(\alpha\) in standard form; so in the following, when we say \(\alpha\) equals something, we mean the standard form for \(\alpha\). While we will mainly be interested in fundamental sequences for countable limit ordinals, it will be convenient to assign fundamental sequences for uncountable limit ordinals as well. The cofinality of an ordinal \(\alpha\) is the smallest cardinality of any set of ordinals whose supremum is \(\alpha\). Since ordinals with uncountable cofinality are not the limits of any countable sequence of ordinals, it makes sense to define fundamental sequences for each ordinal of length equal to its cofinality. The ordinals we discuss will have four possible cofinalities: 0 (for 0), 1 (for successor ordinals), \(\omega\), or \(\Omega\). 0 has cofinality 0 and no fundamental sequence. If \(\alpha = \alpha_1 + \alpha_2 + \ldots \alpha_m\), then cof\((\alpha\)) = cof(\(\alpha_m\)) \(\alpha n = \alpha_1 + \alpha_2 + \ldots \alpha_m n\) If \(\alpha = \omega^0\), then cof\((\alpha\)) = 1 \(\alpha 0 = 0\) If \(\alpha = \omega^\beta\) with cof\((\beta) = 1\), then cof\((\alpha) = \omega\) \(\alpha n = \omega^{\beta0} * n\) If \(\alpha = \omega^\beta\) with cof\((\beta) = \omega\), then cof\((\alpha) = \omega\) \(\alpha n = \omega^{\betan} \) If \(\alpha = \Omega^\gamma \delta\) with cof\((\delta) = \omega\), then cof \((\alpha) = \omega\) \(\alpha n = \Omega^\gamma (\delta n) \) If \(\alpha = \Omega^\gamma \delta\) with cof\((\delta)\) = cof \((\gamma) = 1\), then cof \((\alpha) = \Omega\) \(\alpha \beta = \Omega^\gamma (\delta 0) + \Omega^{\gamma 0} \beta\) If \(\alpha = \Omega^\gamma \delta\) with cof\((\delta) = 1\), cof\((\gamma) = \omega\), then cof \((\alpha) = \omega\) \(\alpha n = \Omega^\gamma (\delta 0) + \Omega^{\gamma n} \) If \(\alpha = \Omega^\gamma \delta\) with cof\((\delta) = 1\), cof\((\gamma) = \Omega\), then cof \((\alpha) = \Omega\) \(\alpha \beta = \Omega^\gamma (\delta 0) + \Omega^{\gamma \beta} \) If \(\alpha = \psi(\beta)\), with cof\((\beta) = 1\), then cof \((\alpha) = \omega\) \(\alpha 0 = \psi(\beta 0) + 1\) \(\alpha n+1 = \omega^{\alpha n} \) If \(\alpha = \psi(\beta)\), with cof\((\beta) = \omega\), then cof \((\alpha) = \omega\) \(\alpha n = \psi(\beta n)\) If \(\alpha = \psi(\beta)\), with cof\((\beta) = \Omega\), then cof \((\alpha) = \omega\) \(\alpha 0 = \psi(\beta 0)\) \(\alpha n+1 = \psi (\beta [n])\) And that's it! Category:Blog posts